package com.lc.projects.structure.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import com.lc.projects.structure.graph.Node.Edge;

//无向图  //未完成，有一些错误。
public class Node {
	public String name;
	public List<Edge> neighbors = new ArrayList<>();

	public Node(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return "Node [name=" + name + ", neighbors=" + neighbors + "]";
	}

	public void addUndirectedEdge(Node destination, int weight) {
		Edge obj = new Edge(destination, weight);
		if (!neighbors.contains(obj)) {
			neighbors.add(obj);
			destination.neighbors.add(new Edge(this, weight));
		}
	}

	public static class Edge {
		public Node destination;
		public int weight;

		public Edge(Node destination, int weight) {
			this.destination = destination;
			this.weight = weight;
		}

		@Override
		public int hashCode() {
			return destination.name.hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			return this.hashCode() == obj.hashCode();
		}

	}
}

class GraphTest {

	Set<Node> open = new HashSet<>();
	Set<Node> close = new HashSet<>();
	Map<String, String> pathInfo = new HashMap<>();
	Map<String, Integer> path = new HashMap<>();

	public void compute(Node start) {
		Node nearest = getShortestPath(start);
		if (nearest == null) {
			return;
		}
		close.add(start);
		open.remove(start);
		List<Edge> list = nearest.neighbors;
		for (Edge obj : list) {
			if (open.contains(obj.destination)) {
				Integer newCompute = (path.get(obj.destination.name) == null ? 0 : path.get(obj.destination.name))
						+ obj.weight;
				if (path.get(obj.destination.name) == null) {
					path.put(obj.destination.name, newCompute);
					pathInfo.put(nearest.name,
							(pathInfo.get(nearest.name) == null ? nearest.name : pathInfo.get(nearest.name)) + "->"
									+ obj.destination.name);
				} else if (path.get(obj.destination.name) > newCompute) {
					path.put(obj.destination.name, newCompute);
					pathInfo.put(nearest.name,
							(pathInfo.get(nearest.name) == null ? nearest.name : pathInfo.get(nearest.name)) + "->"
									+ obj.destination.name);
				}

			}
		}

		compute(nearest);// 向外一层层递归,直至所有顶点被遍历
	}

	/**
	 * 获取与node最近的子节点
	 */
	private Node getShortestPath(Node node) {
		Node res = null;
		int minDis = Integer.MAX_VALUE;
		List<Edge> list = node.neighbors;
		for (Edge child : list) {
			Node temp = child.destination;
			if (open.contains(temp)) { // open表示未遍历
				int distance = child.weight;
				if (distance < minDis) {
					minDis = distance;
					res = temp;
				}
			}
		}
		return res;
	}

	public void print() {
		for (Entry<String, Integer> entry : path.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}

		for (Entry<String, String> entry : pathInfo.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}

	}

	public static void main(String[] args) {
		GraphTest g = new GraphTest();

		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node e = new Node("E");
		a.addUndirectedEdge(c, 5);
		a.addUndirectedEdge(b, 3);
		b.addUndirectedEdge(a, 3);
		b.addUndirectedEdge(d, 2);
		b.addUndirectedEdge(e, 8);
		c.addUndirectedEdge(a, 5);
		c.addUndirectedEdge(d, 6);
		c.addUndirectedEdge(e, 1);
		d.addUndirectedEdge(b, 2);
		d.addUndirectedEdge(c, 6);
		e.addUndirectedEdge(b, 8);
		e.addUndirectedEdge(c, 1);

		g.open.add(b);
		g.open.add(c);
		g.open.add(d);
		g.open.add(e);
		g.close.add(a);

		g.compute(a);
		g.print();

	}
}
